package main

import "container/list"

func reverseList(head *ListNode) *ListNode {
	stack := list.New()

	type stackInfo struct {
		cur        *ListNode
		nextOperId int
		parent     *ListNode
	}

	node := &stackInfo{
		cur:        head,
		nextOperId: 0,
		parent:     nil,
	}

	stack.PushBack(node)
	newHead := head
	for stack.Len() > 0 {
		n := stack.Back().Value.(*stackInfo)
		if n.cur == nil {
			stack.Remove(stack.Back())
			newHead = n.parent
			continue
		}
		if n.nextOperId == 0 {
			n.nextOperId++
			temp := &stackInfo{
				nextOperId: 0,
				cur:        n.cur.Next,
				parent:     n.cur,
			}
			stack.PushBack(temp)
		} else if n.nextOperId == 1 {
			n.cur.Next = n.parent
			stack.Remove(stack.Back())
		}
	}

	return newHead
}
